package com.demo.java.OD451_500.OD476;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【数值同化(E卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146390037
 */
public class OdMain {

    // 定义地图的二维数组，存储道路信息
    public static int[][] road_map;

    // 定义偏移量数组，用于上下左右的移动
    public static int[] offset = {-1, 0, 1, 0, -1};

    public static void main(String[] args) {
        // 创建扫描器对象来接收输入
        Scanner in = new Scanner(System.in);

        // 读取地图的行数和列数
        int m = in.nextInt();
        int n = in.nextInt();

        // 初始化road_map数组，用于存储地图信息
        road_map = new int[m][n];

        // 读取地图信息，赋值给road_map
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                road_map[i][j] = in.nextInt();
            }
        }

        // 从起点(0, 0)开始进行深度优先搜索
        dfs(0, 0, m, n);

        // 统计不是1（已访问或障碍）的区域数量
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 遇到未访问的空地或未探索的区域
                if (road_map[i][j] != 1) {
                    count += 1;
                }
            }
        }

        // 输出最终统计结果
        System.out.println(count);
    }

    /**
     * 字符串分割方法
     *
     * @param input_str 输入的字符串，按照空格分割
     * @return 返回整型数组，包含分割后的数值
     */
    public int[] split(String input_str) {
        // 按空格分割字符串
        String[] tmp2 = input_str.split(" ");

        // 创建一个整数数组来存储分割后的数字
        int[] nums = new int[tmp2.length];

        // 遍历字符串数组，将每个字符串转为整数
        for (int i = 0; i < tmp2.length; i++) {
            nums[i] = Integer.parseInt(tmp2[i]);
        }

        // 返回整数数组
        return nums;
    }

    /**
     * 深度优先搜索（DFS）方法
     * 用于探索地图，从给定的起始坐标开始，访问所有空地
     *
     * @param i 当前坐标的行
     * @param j 当前坐标的列
     * @param m 地图的行数
     * @param n 地图的列数
     */
    public static void dfs(int i, int j, int m, int n) {

        // 如果当前位置已经是目标点（2），则返回
        if (road_map[i][j] == 2) {
            return;
        }

        // 如果当前位置是空地（0），则标记为已访问（1），并继续向四周扩展
        if (road_map[i][j] == 0) {
            road_map[i][j] = 1;

            // 遍历四个方向：上、右、下、左
            for (int index = 0; index < 4; index++) {

                // 判断新的坐标是否合法（即在地图范围内）
                if (0 <= i + offset[index] && i + offset[index] < m && 0 <= j + offset[index + 1] && j + offset[index + 1] < n) {

                    // 递归调用dfs，继续探索周围的空地
                    dfs(i + offset[index], j + offset[index + 1], m, n);
                }
            }
        }
    }
}
